using namespace std;
/*
struct TreeLinkNode {
    int val;
    struct TreeLinkNode *left;
    struct TreeLinkNode *right;
    struct TreeLinkNode *next;
    TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {
        
    }
};
*/
class Solution {
public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode)
    {
        if(pNode == nullptr)
        	return nullptr;
        return findNext(pNode);
    }

    TreeLinkNode *findNext(TreeLinkNode *pNode)
    {
    	//没有右子树
        if(!pNode->right)
    	{
    		TreeLinkNode *father = pNode->next;
    		while(father)
    		{
    			if(father->left == pNode)
    				return father;
    			pNode = father;
    			father = father->next;
    		}
    		return nullptr;
    	}
    	else
    	{
    		TreeLinkNode *right = pNode->right;
    		while(right->left)
    			right = right->left;
    		return right;
    	}
    }
};